{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Score From Removing Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumGain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除子字符串的最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和两个整数 <code>x</code> 和 <code>y</code> 。你可以执行下面两种操作任意次。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>删除子字符串 <code>\"ab\"</code> 并得到 <code>x</code> 分。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>比方说，从 <code>\"c<strong>ab</strong>xbae\"</code> 删除 <code>ab</code> ，得到 <code>\"cxbae\"</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>删除子字符串<code>\"ba\"</code> 并得到 <code>y</code> 分。\n",
    "\t<ul>\n",
    "\t\t<li>比方说，从 <code>\"cabx<strong>ba</strong>e\"</code> 删除 <code>ba</code> ，得到 <code>\"cabxe\"</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回对 <code>s</code> 字符串执行上面操作若干次能得到的最大得分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"cdbcbbaaabab\", x = 4, y = 5\n",
    "<b>输出：</b>19\n",
    "<strong>解释：</strong>\n",
    "- 删除 \"cdbcbbaaa<strong>ba</strong>b\" 中加粗的 \"ba\" ，得到 s = \"cdbcbbaaab\" ，加 5 分。\n",
    "- 删除 \"cdbcbbaa<strong>ab</strong>\" 中加粗的 \"ab\" ，得到 s = \"cdbcbbaa\" ，加 4 分。\n",
    "- 删除 \"cdbcb<strong>ba</strong>a\" 中加粗的 \"ba\" ，得到 s = \"cdbcba\" ，加 5 分。\n",
    "- 删除 \"cdbc<strong>ba</strong>\" 中加粗的 \"ba\" ，得到 s = \"cdbc\" ，加 5 分。\n",
    "总得分为 5 + 4 + 5 + 5 = 19 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"aabbaaxybbaabb\", x = 5, y = 4\n",
    "<b>输出：</b>20\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= x, y &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-score-from-removing-substrings](https://leetcode.cn/problems/maximum-score-from-removing-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-score-from-removing-substrings](https://leetcode.cn/problems/maximum-score-from-removing-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cdbcbbaaabab\"\\n4\\n5', '\"aabbaaxybbaabb\"\\n5\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        #字串 不必连续\n",
    "        cnta =0\n",
    "        cntb=0\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            if i =='a': \n",
    "                if cntb>0 and y>=x:\n",
    "                    cntb -=1\n",
    "                    ans += y\n",
    "                else:\n",
    "                    cnta += 1\n",
    "            elif i =='b':\n",
    "                if cnta>0 and x>=y:\n",
    "                    ans += x\n",
    "                    cnta -=1\n",
    "                else:\n",
    "                    cntb += 1\n",
    "            else:###这个else必不可少\n",
    "                if cnta and cntb:\n",
    "\n",
    "                    ans += min(x,y)*min(cnta,cntb)\n",
    "                cnta =0\n",
    "                cntb =0\n",
    "\n",
    "        if cnta and cntb:\n",
    "            ans += min(x,y)*min(cnta,cntb)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        res = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == 'b':\n",
    "                if x >= y and cnt_a > 0:    # ab 的情况\n",
    "                    res += x\n",
    "                    cnt_a -= 1\n",
    "                else:\n",
    "                    cnt_b += 1\n",
    "            elif c == 'a':\n",
    "                if y > x and cnt_b > 0:     # ba 的情况\n",
    "                    res += y\n",
    "                    cnt_b -= 1\n",
    "                else:\n",
    "                    cnt_a += 1\n",
    "            else:                           #这一个窗口截止了\n",
    "                if cnt_a > 0 and cnt_b > 0:\n",
    "                    res += min(x, y) * min(cnt_a, cnt_b)\n",
    "                cnt_a = 0\n",
    "                cnt_b = 0\n",
    "            \n",
    "        if cnt_a and cnt_b:\n",
    "            res += min(x, y) * min(cnt_a, cnt_b)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        res = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == 'b':\n",
    "                if x >= y and cnt_a > 0:    # ab 的情况\n",
    "                    res += x\n",
    "                    cnt_a -= 1\n",
    "                else:\n",
    "                    cnt_b += 1\n",
    "            elif c == 'a':\n",
    "                if y > x and cnt_b > 0:     # ba 的情况\n",
    "                    res += y\n",
    "                    cnt_b -= 1\n",
    "                else:\n",
    "                    cnt_a += 1\n",
    "            else:                           #这一个窗口截止了\n",
    "                if cnt_a > 0 and cnt_b > 0:\n",
    "                    res += min(x, y) * min(cnt_a, cnt_b)\n",
    "                cnt_a = 0\n",
    "                cnt_b = 0\n",
    "            \n",
    "        if cnt_a and cnt_b:\n",
    "            res += min(x, y) * min(cnt_a, cnt_b)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        cnta = 0\n",
    "        cntb = 0\n",
    "        for i in s+'#':\n",
    "            if i=='a':\n",
    "                if y>x and cntb>0:\n",
    "                    ans += y\n",
    "                    cntb -= 1\n",
    "                else:\n",
    "                    cnta += 1\n",
    "            elif i=='b':\n",
    "                if x>y and cnta>0:\n",
    "                    ans += x\n",
    "                    cnta -= 1\n",
    "                else:\n",
    "                    cntb += 1\n",
    "            else:\n",
    "                if cnta>0 and cntb >0:\n",
    "                    ans += min(x,y)*min(cnta,cntb)\n",
    "                cnta = 0\n",
    "                cntb = 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        a, b =  'a', 'b'\n",
    "        # 默认a = 'a', b = 'b', 如果y > x, 则a = 'b', b = 'a', 并且x与y互换\n",
    "        if y > x:\n",
    "            a, b = 'b', 'a'\n",
    "            x, y = y, x\n",
    "        a_num, b_num = 0, 0\n",
    "        # 对于结尾情况，加上'#'\n",
    "        for ch in s + '#':\n",
    "            if ch == a:\n",
    "                a_num += 1\n",
    "            elif ch == b:\n",
    "                b_num += 1\n",
    "                # 贪心：对于字符b，如果此刻前面还有字符a，则提出字符串ab\n",
    "                if a_num > 0:\n",
    "                    ans += x\n",
    "                    a_num -= 1\n",
    "                    b_num -= 1\n",
    "            else:\n",
    "                # 对于剩下的全是ba字符串，由于没有ab字符串，故min(a_num, b_num)为剩余的ab字符串对，剩余分数为min(a_num, b_num) * y\n",
    "                ans += min(a_num, b_num) * y\n",
    "                a_num, b_num = 0, 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        if x >= y:\n",
    "            c1, c2 = 'a', 'b'\n",
    "        else:\n",
    "            c1, c2 = 'b', 'a'\n",
    "            x, y = y, x\n",
    "        \n",
    "        cnt1, cnt2 = 0, 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if c == c1:\n",
    "                cnt1 += 1\n",
    "            elif c == c2:\n",
    "                if cnt1 > 0:\n",
    "                    cnt1 -= 1\n",
    "                    ans += x\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            else:\n",
    "                continue\n",
    "                \n",
    "            nxt = s[i+1] if i+1 <= n-1 else \" \"\n",
    "            if not nxt in [c1, c2]:\n",
    "                ans += y * min(cnt1, cnt2)\n",
    "                cnt1, cnt2 = 0, 0\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        res = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == 'b':\n",
    "                if x >= y and cnt_a > 0:    # ab 的情况\n",
    "                    res += x\n",
    "                    cnt_a -= 1\n",
    "                else:\n",
    "                    cnt_b += 1\n",
    "            elif c == 'a':\n",
    "                if y > x and cnt_b > 0:     # ba 的情况\n",
    "                    res += y\n",
    "                    cnt_b -= 1\n",
    "                else:\n",
    "                    cnt_a += 1\n",
    "            else:                           #这一个窗口截止了\n",
    "                if cnt_a > 0 and cnt_b > 0:\n",
    "                    res += min(x, y) * min(cnt_a, cnt_b)\n",
    "                cnt_a = 0\n",
    "                cnt_b = 0\n",
    "            \n",
    "        if cnt_a and cnt_b:\n",
    "            res += min(x, y) * min(cnt_a, cnt_b)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        if x >= y:\n",
    "            c1, c2 = 'a', 'b'\n",
    "        else:\n",
    "            x, y = y, x\n",
    "            c1, c2 = 'b', 'a'\n",
    "        \n",
    "        n = len(s)\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == c1:\n",
    "                cnt1 += 1\n",
    "            elif c == c2:\n",
    "                if cnt1 >= 1:\n",
    "                    ans += x\n",
    "                    cnt1 -= 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            else:\n",
    "                continue\n",
    "            nxt = s[i+1] if i+1<=n-1 else \" \"\n",
    "            # 下一个是分割情况\n",
    "            if not nxt in [c1, c2]:\n",
    "                ans += y * min(cnt1, cnt2)\n",
    "                cnt1, cnt2 = 0, 0\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        if x >= y:\n",
    "            c1, c2 = 'a', 'b'\n",
    "        else:\n",
    "            c1, c2 = 'b', 'a'\n",
    "            x, y = y, x\n",
    "        \n",
    "        cnt1, cnt2 = 0, 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if c == c1:\n",
    "                cnt1 += 1\n",
    "            elif c == c2:\n",
    "                if cnt1 > 0:\n",
    "                    cnt1 -= 1\n",
    "                    ans += x\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            nxt = s[i+1] if i+1 <= n-1 else \" \"\n",
    "            if not nxt in [c1, c2]:\n",
    "                ans += y * min(cnt1, cnt2)\n",
    "                cnt1, cnt2 = 0, 0\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        #字串 不必连续\n",
    "        cnta =0\n",
    "        cntb=0\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            if i =='a': \n",
    "                if cntb>0 and y>=x:\n",
    "                    cntb -=1\n",
    "                    ans += y\n",
    "                else:\n",
    "                    cnta += 1\n",
    "            elif i =='b':\n",
    "                if cnta>0 and x>=y:\n",
    "                    ans += x\n",
    "                    cnta -=1\n",
    "                else:\n",
    "                    cntb += 1\n",
    "            else:\n",
    "                if cnta and cntb:\n",
    "\n",
    "                    ans += min(x,y)*min(cnta,cntb)\n",
    "                cnta =0\n",
    "                cntb =0\n",
    "\n",
    "        if cnta and cntb:\n",
    "            ans += min(x,y)*min(cnta,cntb)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        if x >= y:\n",
    "            c1, c2 = 'a', 'b'\n",
    "        else:\n",
    "            c1, c2 = 'b', 'a'\n",
    "            x, y = y, x\n",
    "        \n",
    "        cnt1, cnt2 = 0, 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if c == c1:\n",
    "                cnt1 += 1\n",
    "            elif c == c2:\n",
    "                if cnt1 > 0:\n",
    "                    cnt1 -= 1\n",
    "                    ans += x\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "\n",
    "\n",
    "            nxt = s[i+1] if i+1 <= n-1 else \" \"\n",
    "            if not nxt in [c1, c2]:\n",
    "                ans += y * min(cnt1, cnt2)\n",
    "                cnt1, cnt2 = 0, 0\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        self.ans=0\n",
    "        def helper(s,x,ab):\n",
    "            i=0\n",
    "            while i<len(s):\n",
    "                while s[i:i+2]==ab:\n",
    "                    self.ans+=x\n",
    "                    s=s[:i]+s[i+2:]\n",
    "                    i=max(0,i-1)\n",
    "                i+=1\n",
    "            return s\n",
    "        if x>y:helper(helper(s,x,'ab'),y,'ba')\n",
    "        else: helper(helper(s,y,'ba'),x,'ab')\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        # 贪心的策略吧\n",
    "        if x >= y:\n",
    "            ans = 0\n",
    "            while 'ab' in s:\n",
    "                n = len(s)\n",
    "                s = s.replace('ab', '')\n",
    "                n1 = len(s)\n",
    "                ans += (n - n1) // 2 * x\n",
    "            while 'ba' in s:\n",
    "                n = len(s)\n",
    "                s = s.replace('ba', '')\n",
    "                n1 = len(s)\n",
    "                ans += (n - n1) // 2 * y\n",
    "        else:\n",
    "            ans = 0\n",
    "            while 'ba' in s:\n",
    "                n = len(s)\n",
    "                s = s.replace('ba', '')\n",
    "                n1 = len(s)\n",
    "                ans += (n - n1) // 2 * y\n",
    "            while 'ab' in s:\n",
    "                n = len(s)\n",
    "                s = s.replace('ab', '')\n",
    "                n1 = len(s)\n",
    "                ans += (n - n1) // 2 * x\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        a, b =  'a', 'b'\n",
    "        if y > x:\n",
    "            a, b = 'b', 'a'\n",
    "            x, y = y, x\n",
    "        a_num, b_num = 0, 0\n",
    "        for ch in s + '#':\n",
    "            if ch == a:\n",
    "                a_num += 1\n",
    "            elif ch == b:\n",
    "                b_num += 1\n",
    "                if a_num > 0:\n",
    "                    ans += x\n",
    "                    a_num -= 1\n",
    "                    b_num -= 1\n",
    "            else:\n",
    "                ans += min(a_num, b_num) * y\n",
    "                a_num, b_num = 0, 0\n",
    "            # print(ch, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        if x >= y:\n",
    "            c1, c2 = 'a', 'b'\n",
    "        else:\n",
    "            x, y = y, x\n",
    "            c1, c2 = 'b', 'a'\n",
    "        \n",
    "        n = len(s)\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == c1:\n",
    "                cnt1 += 1\n",
    "            elif c == c2:\n",
    "                if cnt1 >= 1:\n",
    "                    ans += x\n",
    "                    cnt1 -= 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            nxt = s[i+1] if i+1<=n-1 else \" \"\n",
    "            # 下一个是分割情况\n",
    "            if not nxt in [c1, c2]:\n",
    "                ans += y * min(cnt1, cnt2)\n",
    "                cnt1, cnt2 = 0, 0\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if x < y:\n",
    "            return self.maximumGain(s[::-1], y, x)\n",
    "        ans = 0\n",
    "        a, b = 0, 0\n",
    "        for v in s:\n",
    "            if v == 'b':\n",
    "                if a > 0:\n",
    "                    ans += x\n",
    "                    a -= 1\n",
    "                else:\n",
    "                    b += 1\n",
    "            elif v == 'a':\n",
    "                a += 1\n",
    "            else:\n",
    "                ans += min(a, b) * y\n",
    "                a, b = 0, 0\n",
    "        return ans + y * min(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if(x > y):\n",
    "            first, second = 'ab', 'ba'\n",
    "        else:\n",
    "            first, second = 'ba', 'ab'\n",
    "            x, y = y, x\n",
    "        result = 0\n",
    "        st = ''\n",
    "        for c in s:\n",
    "            st += c \n",
    "            if(len(st) >= 2 and st[-2:] == first):\n",
    "                result += x \n",
    "                st = st[:-2]\n",
    "\n",
    "        s = st \n",
    "        st = ''\n",
    "        for c in s:\n",
    "             st += c\n",
    "             if(len(st) >= 2 and st[-2:] == second):\n",
    "                 result += y \n",
    "                 st = st[:-2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if(x > y):\n",
    "            first, second = 'ab', 'ba'\n",
    "        else:\n",
    "            first, second = 'ba', 'ab'\n",
    "            x, y = y, x\n",
    "        result = 0\n",
    "        st = ''\n",
    "        for c in s:\n",
    "            st += c \n",
    "            if(len(st) >= 2 and st[-2:] == first):\n",
    "                result += x \n",
    "                st = st[:-2]\n",
    "        s = st \n",
    "        st = ''\n",
    "        for c in s:\n",
    "             st += c\n",
    "             if(len(st) >= 2 and st[-2:] == second):\n",
    "                 result += y \n",
    "                 st = st[:-2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if(x > y):\n",
    "            first, second = 'ab', 'ba'\n",
    "        else:\n",
    "            first, second = 'ba', 'ab'\n",
    "            x, y = y, x\n",
    "        result = 0\n",
    "        st = ''\n",
    "        for c in s:\n",
    "            st += c \n",
    "            if(len(st) >= 2 and st[-2:] == first):\n",
    "                result += x \n",
    "                st = st[:-2]\n",
    "\n",
    "        s = st \n",
    "        st = ''\n",
    "        for c in s:\n",
    "             st += c\n",
    "             if(len(st) >= 2 and st[-2:] == second):\n",
    "                 result += y \n",
    "                 st = st[:-2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if(x > y):\n",
    "            first, second = 'ab', 'ba'\n",
    "        else:\n",
    "            first, second = 'ba', 'ab'\n",
    "            x, y = y, x\n",
    "        result = 0\n",
    "        st = ''\n",
    "        for c in s:\n",
    "            st += c \n",
    "            if(len(st) >= 2 and st[-2:] == first):\n",
    "                result += x \n",
    "                st = st[:-2]\n",
    "        s = st \n",
    "        st = ''\n",
    "        for c in s:\n",
    "             st += c\n",
    "             if(len(st) >= 2 and st[-2:] == second):\n",
    "                 result += y \n",
    "                 st = st[:-2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\r\n",
    "        res = 0 \r\n",
    "        if x > y:\r\n",
    "            prex = 'a'\r\n",
    "        else:\r\n",
    "            prex = 'b'\r\n",
    "        def sovle(a:str)-> int:\r\n",
    "            resa = 0\r\n",
    "            sta = []\r\n",
    "            for ch in a:\r\n",
    "                if ch == prex:\r\n",
    "                    sta.append(ch)\r\n",
    "                else:\r\n",
    "                    if sta and sta[-1] == prex:\r\n",
    "                        resa += max(x, y)\r\n",
    "                        sta.pop()\r\n",
    "                    else:\r\n",
    "                        sta.append(ch)\r\n",
    "            cp = 0\r\n",
    "            for ch in sta:\r\n",
    "                if ch == prex:\r\n",
    "                    cp += 1 \r\n",
    "            cnt = min(cp, len(sta) - cp)\r\n",
    "            resa += cnt * min(x, y)\r\n",
    "            return resa\r\n",
    "\r\n",
    "            pass \r\n",
    "        i = 0 \r\n",
    "        while i < len(s):\r\n",
    "            if s[i] == 'a' or s[i] == 'b':\r\n",
    "                j = i \r\n",
    "                while j < len(s) and s[j] in \"ab\":\r\n",
    "                    j += 1 \r\n",
    "                res += sovle(s[i:j])\r\n",
    "                i = j + 1\r\n",
    "            else:\r\n",
    "                i += 1\r\n",
    "        return res \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        lst = [\"\"]\n",
    "        for ch in s:\n",
    "            if ch == \"a\" or ch == \"b\":\n",
    "                lst[-1] += ch\n",
    "            else:\n",
    "                if lst[-1] != \"\":\n",
    "                    lst.append(\"\")\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for ss in lst:\n",
    "            # 计算总数的最大值\n",
    "            max_num = min(ss.count(\"a\"), ss.count(\"b\"))\n",
    "\n",
    "            if x >= y:\n",
    "                # 计算ab数量的最大值\n",
    "                max_n1 = 0\n",
    "                count = 0\n",
    "                for ch in ss:\n",
    "                    if ch == \"a\":\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        if count > 0:\n",
    "                            count -= 1\n",
    "                            max_n1 += 1\n",
    "\n",
    "                # 计算最终结果\n",
    "                ans += max_n1 * x + (max_num - max_n1) * y\n",
    "\n",
    "            else:\n",
    "                # 计算ba数量的最大值\n",
    "                max_n2 = 0\n",
    "                count = 0\n",
    "                for ch in ss:\n",
    "                    if ch == \"b\":\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        if count > 0:\n",
    "                            count -= 1\n",
    "                            max_n2 += 1\n",
    "\n",
    "                # 计算最终结果\n",
    "                ans += max_n2 * y + (max_num - max_n2) * x\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        q=[]\n",
    "        ans=0\n",
    "        if x>y:\n",
    "          x,y=y,x\n",
    "          s=s[::-1]\n",
    "       \n",
    "        for c in s:\n",
    "          if c=='a':\n",
    "             if q and q[-1]=='b':\n",
    "                q.pop(-1)\n",
    "                ans+=y\n",
    "             else:\n",
    "                q.append(c)    \n",
    "                \n",
    "          else:\n",
    "              q.append(c)\n",
    "        m=[]      \n",
    "        while q:\n",
    "           c=q.pop(-1)\n",
    "           if c=='a':\n",
    "              if m and m[-1]=='b':\n",
    "                 ans+=x\n",
    "                 m.pop(-1)\n",
    "              else:\n",
    "                 m.append(c)    \n",
    "           else:\n",
    "                 m.append(c)\n",
    "        return ans                \n",
    "                          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, a: int, b: int) -> int:\n",
    "        stk = []\n",
    "        ans = 0\n",
    "        if a < b:\n",
    "            a, b = b, a \n",
    "            s = s[::-1]\n",
    "        for x in s:\n",
    "            if x == \"a\":stk.append(\"a\")\n",
    "            elif x == \"b\":\n",
    "                if stk and stk[-1] == \"a\":\n",
    "                    stk.pop()\n",
    "                    ans += a\n",
    "                else:\n",
    "                    stk.append(\"b\")\n",
    "            else:\n",
    "                ans += b * min(stk.count(\"a\"), stk.count(\"b\"))\n",
    "                stk = []\n",
    "        return ans + b * min(stk.count(\"a\"), stk.count(\"b\"))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        # 核心思想 例如：cdbcbbaaabab可以分为b和bbaaabab两个字串，aabbaaxybbaabb可以分为aabbaa，bbaabb\n",
    "        # 结论：每个字串都可以这样分，分出来的字串比如aabbaa不论你删除ab,还是ba，还是ab,ba混合删除，你的最大删除次数是不变的都是两次\n",
    "        # 所以我们只需要优先删除分数大的，在删除分数小的\n",
    "        # 我们用栈来模拟删除\n",
    "        first = 'a'\n",
    "        second = 'b'\n",
    "        # 保证x是分数多的 即 first->second\n",
    "        if y > x:\n",
    "            x,y = y,x\n",
    "            first,second = second,first\n",
    "        # 统计分数多的\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for ch in s:\n",
    "            if not st:\n",
    "                st.append(ch)\n",
    "            else:\n",
    "                if ch == second and st[-1] == first:\n",
    "                    ans += x\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    st.append(ch)\n",
    "        # 统计分数少的\n",
    "        st2 = []\n",
    "        for ch in st:\n",
    "            if not st2:\n",
    "                st2.append(ch)\n",
    "            else:\n",
    "                if ch == first and st2[-1] == second:\n",
    "                    ans += y\n",
    "                    st2.pop()\n",
    "                else:\n",
    "                    st2.append(ch)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        # 初始化得分\n",
    "        score = 0\n",
    "        \n",
    "        # 根据x和y的大小来确定首先删除哪个子字符串\n",
    "        if x > y:\n",
    "            first, second, first_score, second_score = \"a\", \"b\", x, y\n",
    "        else:\n",
    "            first, second, first_score, second_score = \"b\", \"a\", y, x\n",
    "        \n",
    "        # 第一次迭代\n",
    "        stack1 = []\n",
    "        for char in s:\n",
    "            if char == second and stack1 and stack1[-1] == first:\n",
    "                stack1.pop()\n",
    "                score += first_score\n",
    "            else:\n",
    "                stack1.append(char)\n",
    "        \n",
    "        # 第二次迭代\n",
    "        stack2 = []\n",
    "        for char in stack1:\n",
    "            if char == first and stack2 and stack2[-1] == second:\n",
    "                stack2.pop()\n",
    "                score += second_score\n",
    "            else:\n",
    "                stack2.append(char)\n",
    "        \n",
    "        return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        # ans = 0\n",
    "        # stack = []\n",
    "        # target_x, target_y = 'ab', 'ba'\n",
    "\n",
    "        # def process_str(str_s):\n",
    "        #     nonlocal ans\n",
    "        #     Flag = True\n",
    "        #     while Flag:\n",
    "        #         Flag = False\n",
    "        #         count = str_s.count(target_x)\n",
    "        #         if count:\n",
    "        #             Flag = True\n",
    "        #             ans += (count * x)\n",
    "        #             str_s = str_s.replace(target_x, '')\n",
    "        #         if not Flag:\n",
    "        #             count_n = str_s.count(target_y)\n",
    "        #             if count_n:\n",
    "        #                 Flag = True\n",
    "        #                 ans += (count_n * y)\n",
    "        #                 str_s = str_s.replace(target_y, '')\n",
    "\n",
    "\n",
    "        # if x == y:\n",
    "        #     for ch in s:\n",
    "        #         if ch in 'ab':\n",
    "        #             if not stack:\n",
    "        #                 stack.append(ch)\n",
    "        #             else:\n",
    "        #                 if stack[-1] + ch in (\"ab\", 'ba'):\n",
    "        #                     stack.pop()\n",
    "        #                     ans += x\n",
    "        #         else:\n",
    "        #             stack.clear()\n",
    "        # else:\n",
    "        #     if y > x:\n",
    "        #         target_x, target_y = 'ba', 'ab'\n",
    "        #         x, y = y, x\n",
    "        #     temp = ''\n",
    "        #     for ch in s:\n",
    "        #         if ch in 'ab':\n",
    "        #             temp += ch\n",
    "        #         else:\n",
    "        #             if temp:\n",
    "        #                 process_str(temp)\n",
    "        #                 temp = ''\n",
    "        #     else:\n",
    "        #         if temp:\n",
    "        #             process_str(temp)\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        target_x, target_y = 'ab', 'ba'\n",
    "        if y > x:\n",
    "            target_x, target_y = 'ba', 'ab'\n",
    "            x, y = y, x\n",
    "        for ch in s:\n",
    "            if stack and stack[-1] + ch == target_x:\n",
    "                stack.pop()\n",
    "                ans += x\n",
    "            else:\n",
    "                stack.append(ch)\n",
    "\n",
    "        temp_t = []\n",
    "        for ch in stack:\n",
    "            if temp_t and temp_t[-1] + ch == target_y:\n",
    "                temp_t.pop()\n",
    "                ans += y\n",
    "            else:\n",
    "                temp_t.append(ch)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, a: int, b: int) -> int:\n",
    "        stk = []\n",
    "        ans = 0\n",
    "        if a < b:\n",
    "            a, b = b, a \n",
    "            s = s[::-1]\n",
    "        for x in s:\n",
    "            if x == \"a\":stk.append(\"a\")\n",
    "            elif x == \"b\":\n",
    "                if stk and stk[-1] == \"a\":\n",
    "                    stk.pop()\n",
    "                    ans += a\n",
    "                else:\n",
    "                    stk.append(\"b\")\n",
    "            else:\n",
    "                ans += b * min(stk.count(\"a\"), stk.count(\"b\"))\n",
    "                print(stk)\n",
    "                stk = []\n",
    "        return ans + b * min(stk.count(\"a\"), stk.count(\"b\"))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if x > y:\n",
    "            first, second = \"a\", \"b\"\n",
    "        else:\n",
    "            first, second = \"b\", \"a\"\n",
    "            x, y = y, x\n",
    "\n",
    "        res = 0\n",
    "        stk = []\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            ch = s[i]\n",
    "            if stk and stk[-1] == first and ch == second:\n",
    "                res += x\n",
    "                stk.pop()\n",
    "            else:\n",
    "                stk.append(ch)\n",
    "\n",
    "        s = \"\".join(stk)\n",
    "        stk = []\n",
    "        for i in range(len(s)):\n",
    "            ch = s[i]\n",
    "            if stk and stk[-1] == second and ch == first:\n",
    "                res += y\n",
    "                stk.pop()\n",
    "            else:\n",
    "                stk.append(ch)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def remove1(s, x):\n",
    "            nonlocal ans\n",
    "\n",
    "            q = list()\n",
    "            n = len(s)\n",
    "            for i in range(n):\n",
    "                c = s[i]    \n",
    "                if q and q[-1] =='a' and c == 'b':\n",
    "                    ans += x\n",
    "                    q.pop()\n",
    "                else:\n",
    "                    q.append(c)\n",
    "            return \"\".join(q)\n",
    "        \n",
    "        def remove2(s, y):\n",
    "            nonlocal ans\n",
    "\n",
    "            q = list()\n",
    "            n = len(s)\n",
    "            for i in range(n):\n",
    "                c = s[i]\n",
    "                if q and q[-1] == 'b' and c == 'a':\n",
    "                    ans += y\n",
    "                    q.pop()\n",
    "                else:\n",
    "                    q.append(c)\n",
    "\n",
    "            return \"\".join(q)\n",
    "        \n",
    "        if x >= y:\n",
    "            s = remove1(s, x)\n",
    "            s = remove2(s, y)\n",
    "        else:\n",
    "            s = remove2(s, y)\n",
    "            s = remove1(s, x)\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "\n",
    "        def check(st, target, score):\n",
    "            res = 0\n",
    "            a, b = target[0], target[1]\n",
    "            stack = []\n",
    "            for w in st:\n",
    "                if w == b:\n",
    "                    if stack and stack[-1] == a:\n",
    "                        stack.pop()\n",
    "                        res += score\n",
    "                    else:\n",
    "                        stack.append(w)\n",
    "                else:\n",
    "                    stack.append(w)\n",
    "\n",
    "            rest = \"\".join(stack)\n",
    "            return res, rest\n",
    "\n",
    "        if x >= y:\n",
    "            ans, word = check(s, \"ab\", x)\n",
    "            ans += check(word, \"ba\", y)[0]\n",
    "        else:\n",
    "            ans, word = check(s, \"ba\", y)\n",
    "            ans += check(word, \"ab\", x)[0]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "        def count(s, cost, target):\n",
    "            nonlocal ans\n",
    "            stack = []\n",
    "            for c in s:\n",
    "                if stack and stack[-1] + c == target:\n",
    "                    stack.pop()\n",
    "                    ans += cost\n",
    "                else:\n",
    "                    stack.append(c)\n",
    "            return stack\n",
    "        if x >= y:\n",
    "            stack = count(s, x, 'ab')\n",
    "            count(stack, y, 'ba')\n",
    "        else:\n",
    "            stack = count(s, y, 'ba')\n",
    "            count(stack, x, 'ab')\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "      def helper(s,char):\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "          if not stack or stack[-1]+i !=char:\n",
    "            stack.append(i)\n",
    "          else:\n",
    "            stack.pop()\n",
    "            ans +=1\n",
    "        return ''.join(stack),ans\n",
    "      if x >=y:\n",
    "        s,t = helper(s,'ab')\n",
    "        res =t*x + helper(s,'ba')[1]*y\n",
    "      else:\n",
    "        s,t = helper(s,'ba')\n",
    "        res = t*y + helper(s,'ab')[1]*x\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        res=0\n",
    "        def count(s, target, score):\n",
    "            nonlocal res\n",
    "            n = len(s)\n",
    "            stack = []\n",
    "            for i in range(n):\n",
    "                if stack and stack[-1] + s[i] == target:\n",
    "                    stack.pop()\n",
    "                    res += score\n",
    "                else:\n",
    "                    stack.append(s[i])\n",
    "            return ''.join(stack)\n",
    "        \n",
    "        if x > y:\n",
    "            stack = count(s, \"ab\", x)\n",
    "            count(stack, \"ba\", y)\n",
    "        else:            \n",
    "            stack = count(s, \"ba\", y)\n",
    "            count(stack, \"ab\", x)    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        stack = []\n",
    "        result = 0\n",
    "        group = \"ab\" if x >= y else \"ba\"\n",
    "        score1 = max(x, y)\n",
    "        score2 = min(x, y)\n",
    "        # 以ab > ba为例\n",
    "        # 优先找ab的, 有一个就匹配一个\n",
    "        # 然后ab匹配完之后, 只会有ba的情况, 此时逆过来找就ok\n",
    "        for index, c in enumerate(s):\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "                continue\n",
    "\n",
    "            if c == group[1]:\n",
    "                if stack[-1] == group[0]:\n",
    "                    stack.pop()\n",
    "                    result += score1\n",
    "                else:\n",
    "                    stack.append(c)\n",
    "            elif c == group[0]:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                r_stack = []\n",
    "                while stack:\n",
    "                    elem = stack.pop()\n",
    "                    if r_stack and r_stack[-1] == group[0] and elem == group[1]:\n",
    "                        r_stack.pop()\n",
    "                        result += score2\n",
    "                    else:\n",
    "                        r_stack.append(elem)\n",
    "        r_stack = []\n",
    "        while stack:\n",
    "            elem = stack.pop()\n",
    "            if r_stack and r_stack[-1] == group[0] and elem == group[1]:\n",
    "                r_stack.pop()\n",
    "                result += score2\n",
    "            else:\n",
    "                r_stack.append(elem)\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def remove(s, x, c1, c2):\n",
    "            nonlocal ans\n",
    "            q = []\n",
    "            n = len(s)\n",
    "            for i, c in enumerate(s):\n",
    "                if q and q[-1] == c1 and c == c2:\n",
    "                    ans += x\n",
    "                    q.pop()\n",
    "                else:\n",
    "                    q.append(c)\n",
    "            return \"\".join(q)\n",
    "        \n",
    "        if x >= y:\n",
    "            s = remove(s, x, 'a', 'b')\n",
    "            s = remove(s, y, 'b', 'a')\n",
    "        else:\n",
    "            s = remove(s, y, 'b', 'a')\n",
    "            s = remove(s, x, 'a', 'b')\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        if x>y:\n",
    "            first = 'ab'\n",
    "            second = 'ba'            \n",
    "        else:\n",
    "            first='ba'\n",
    "            second = 'ab'\n",
    "\n",
    "        \n",
    "        def cutstr(lst, subs, ans, addv):\n",
    "            n = len(lst)\n",
    "            if n<=1:\n",
    "                return [], ans\n",
    "            dq = [lst[0]]\n",
    "            for i in range(1,n):\n",
    "                if lst[i]==subs[1]:\n",
    "                    if len(dq)>=1 and dq[-1]==subs[0]:\n",
    "                        dq.pop()\n",
    "                        ans+=addv\n",
    "                        continue\n",
    "                dq.append(lst[i])\n",
    "            return dq, ans\n",
    "        \n",
    "        ans = 0\n",
    "        curs, ans = cutstr(s, first, ans, max(x,y))\n",
    "        curs, ans = cutstr(curs, second, ans, min(x,y))\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "    \n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        # 贪心 栈\n",
    "        # 默认 x >= y\n",
    "        first = \"a\"\n",
    "        second = \"b\"\n",
    "        if y > x:  # 如果y>x, 进行变量调换\n",
    "            x, y = y, x\n",
    "            first, second = second, first\n",
    "        ans = 0\n",
    "        stack = [] \n",
    "        for char in s:\n",
    "            if not stack:\n",
    "                stack.append(char)\n",
    "            else:\n",
    "                if char == second and stack[-1] == first:\n",
    "                    stack.pop()\n",
    "                    ans += x\n",
    "                else:\n",
    "                    stack.append(char)\n",
    "\n",
    "        stack1 = []\n",
    "        for char in stack: # 处理榨取高分字母组合之后剩下的， 继续榨取低分组合\n",
    "            if not stack1:\n",
    "                stack1.append(char)\n",
    "            else:\n",
    "                if char == first and stack1[-1] == second:\n",
    "                    stack1.pop()\n",
    "                    ans += y\n",
    "                else:\n",
    "                    stack1.append(char)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ans=0\n",
    "        n=len(s)\n",
    "        \n",
    "        if x>y:\n",
    "            q=[]\n",
    "            for i in s:\n",
    "                q.append(i)\n",
    "                if q[-2:]==['a','b']:\n",
    "                    ans+=x\n",
    "                    q.pop()\n",
    "                    q.pop()\n",
    "            s=''.join(q)\n",
    "\n",
    "            q=[]\n",
    "            for i in s:\n",
    "                q.append(i)\n",
    "                if q[-2:]==['b','a']:\n",
    "                    ans+=y\n",
    "                    q.pop()\n",
    "                    q.pop()\n",
    "\n",
    "        else:\n",
    "            q=[]\n",
    "            for i in s:\n",
    "                q.append(i)\n",
    "                if q[-2:]==['b','a']:\n",
    "                    ans+=y\n",
    "                    q.pop()\n",
    "                    q.pop()\n",
    "            s=''.join(q)\n",
    "            q=[]\n",
    "            for i in s:\n",
    "                q.append(i)\n",
    "                if q[-2:]==['a','b']:\n",
    "                    ans+=x\n",
    "                    q.pop()\n",
    "                    q.pop()\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        ca = 0\n",
    "        cb = 0\n",
    "        cnt = 0\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        if x > y:\n",
    "            x, y = y, x\n",
    "            for i in range(n):\n",
    "                if s[i] == 'a':\n",
    "                    res.append('b')\n",
    "                elif s[i] == 'b':\n",
    "                    res.append('a')\n",
    "                else:\n",
    "                    res.append(s[i])\n",
    "        else:\n",
    "            for i in range(n):\n",
    "                res.append(s[i])\n",
    "        for c in res:\n",
    "            if c == 'b':\n",
    "                cb += 1\n",
    "            elif c == 'a':\n",
    "                if cb:\n",
    "                    cnt += y\n",
    "                    cb -= 1\n",
    "                    print(cnt)\n",
    "                else:\n",
    "                    ca += 1\n",
    "            else:\n",
    "                cnt += min(ca, cb) * x\n",
    "                ca = 0\n",
    "                cb = 0\n",
    "\n",
    "        cnt += min(ca, cb) * x\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGain(self, s: str, x: int, y: int) -> int:\n",
    "        stack = []\n",
    "        result = 0\n",
    "        group = \"ab\" if x >= y else \"ba\"\n",
    "        score1 = max(x, y)\n",
    "        score2 = min(x, y)\n",
    "        for index, c in enumerate(s):\n",
    "            if not stack:\n",
    "                stack.append(c)\n",
    "                continue\n",
    "\n",
    "            if c == group[1]:\n",
    "                if stack[-1] == group[0]:\n",
    "                    stack.pop()\n",
    "                    result += score1\n",
    "                else:\n",
    "                    stack.append(c)\n",
    "            elif c == group[0]:\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                r_stack = []\n",
    "                while stack:\n",
    "                    elem = stack.pop()\n",
    "                    if r_stack and r_stack[-1] == group[0] and elem == group[1]:\n",
    "                        r_stack.pop()\n",
    "                        result += score2\n",
    "                    else:\n",
    "                        r_stack.append(elem)\n",
    "        r_stack = []\n",
    "        while stack:\n",
    "            elem = stack.pop()\n",
    "            if r_stack and r_stack[-1] == group[0] and elem == group[1]:\n",
    "                r_stack.pop()\n",
    "                result += score2\n",
    "            else:\n",
    "                r_stack.append(elem)\n",
    "                \n",
    "        return result\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
